Reprezentacja danych w pamięci

Część II - Systemy liczbowe

Odkąd wynaleziono pieniądze i koło, ludzie zaczęli kręcić interesy :) Równie dawno temu ludzie zaczęli liczyć. Policzyć trzeba było nie tylko pieniądze, ale np. upolowane mamuty i inne mniejsze albo większe rzeczy.

Liczby trzeba było jakoś zapisywać. Powstały więc różne sposoby na to. Na co dzień posługujemy się systemem dziesiętnym oraz cyframi arabskimi. Jednak znamy też np. cyfry rzymskie. Także podział na 10, 100 czy 1000 części nie jest wcale tak oczywisty, jak mogłoby się wydawać patrząc na jednostki miar takie, jak kilometr, centymetr czy kilogram. Doba ma przecież 24 godziny, a godzina 60 sekund.

To wszystko są pozostałości po przeszłości, które uświadamiają nam względność naszego sposobu liczenia i możliwość tworzenia nieskończenie wielu różnych, nowych sposobów zapisywania liczb.

Teoria

Poznamy teraz różne systemy liczbowe oraz nauczymy się zapisywać liczby w dowolnym z nich i zamieniać między nimi.

Na początek porcja nieco ciężkostrawnej teorii, którą jednak trzeba jakoś przetrawić :)

Wstęp

Zastanówmy się przez chwilę, w jaki sposób zapisywane są liczby. Dowolnie dużą liczbę jesteśmy w stanie zapisać za pomocą pewnej ilości cyfr, których mamy do dyspozycji dziesięć: 0, 1, 2, 3, 4, 5, 6, 7, 8 i 9. Stąd nazwa naszego systemu – system dziesiętny.

Jednak cyfra cyfrze nierówna. Na przykład w liczbie 123, cyfra 1 ma inne znaczenie niż cyfra 2 czy 3. Ta pierwsza nazwana bywa cyfrą setek, druga – cyfrą dziesiątek, ostatnia zaś – cyfrą jedności.

Skąd te nazwy? Zauważmy, że 1, 10, 100 itd. to kolejne potęgi liczby 10 – która jest podstawą naszego systemu dziesiętnego.

10⁰ = 1

10¹ = 10

10² = 100

10³ = 1000

itd.

Wynika z tego, że nasze używane na co dzień cyfry arabskie w systemie dziesiętnym są systemem pozycyjnym wagowym. Cyfry rzymskie są wyłącznie systemem pozycyjnym, bo poszczególne pozycje cyfr nie mają w nim przypisanych na stałe wag, takich jak 1, 10, 100 itd.

Zostawmy już cyfry rzymskie w spokoju i zajmijmy się normalnymi cyframi arabskimi. Pomyślmy co by było, gdyby do zapisywania liczb używać innej ilości cyfr – np. tylko pięciu? Za ich pomocą także dałoby się zapisać dowolną liczbę. Rodzi się jednak pytanie: jakie byłyby to cyfry?

Wzór

A teraz uwaga, bo będzie straszny wzór ;)

Pokaże nam on, w jaki sposób „zbudowana jest” każda liczba w dowolnym systemie.

m, n Î C, m Ł 0, n ł 0, m Ł n

L to nasza liczba.

N to podstawa systemu (np. 10 dla systemu dziesiętnego).

m to indeks ostatniej cyfry (tej z prawej strony), albo inaczej mówiąc liczba przeciwna do ilości cyfr po przecinku, np. w liczbie 1984.0415 m=-4.

n to indeks pierwszej cyfry (tej z lewej strony), albo inaczej mówiąc ilość cyfr przed przecinkiem pomniejszona o 1, np. w liczbie 1984.0415 n=3.

Wynika z tego, że pierwsza cyfra przed przecinkiem ma indeks 0, poprzednie cyfry mają kolejne indeksy dodatnie, a cyfry po przecinku mają kolejne indeksy ujemne numerowane w drugą stronę.

i to indeksy kolejnych cyfr.

a_i to kolejne cyfry w naszej liczbie.

Przykład

Możemy już przystąpić do przeliczenia liczby z jakiegoś systemu na system dziesiętny. Weźmy liczbę (320)₅. Rozwijając ją wg przedstawionego wyżej wzoru mamy:

(320)₅ = 3*5² + 2*5¹ + 0*5⁰ = 3*25 + 2*5 + 0*1 = 75 + 10 + 0 = 85

Okazuje się, że liczba (320)₅ zapisana w systemie piątkowym przyjmuje w systemie dziesiętnym postać liczby 85.

Nie mniej ważne od zapisywania jest odpowiednie czytanie liczb. Liczby w systemie innym niż dziesiętny nie wolno czytać tak, jak np. „trzysta dwadzieścia”! Należy mówić zawsze „trzy, dwa, zero”.

Dlaczego? Zauważ, co oznaczają tamte słowa. „Trzysta dwadzieścia” to „trzy setki” i „dwie dziesiątki”. Nieświadomie mówimy więc w ten sposób o cyfrze setek i cyfrze dziesiątek, a te kolejne potęgi dziesiątki są wagami kolejnych cyfr jedynie w systemie dziesiętnym.

Patrząc na powyższy przykład można przy okazji wysnuć wniosek, że w systemie piątkowym mamy do czynienia z „cyfrą dwudziestek piątek”, „cyfrą piątek” i „cyfrą jedności”, a wcześniej zapewne z „cyfrą sto dwudziestek piątek” (bo 5³ = 125).

Ćwiczenia

Począwszy od tego miejsca zamieszczał będę zadania do samodzielnego wykonania wraz z odpowiedziami w przypisie. Mocno zalecam wykonanie przynajmniej niektórych z nich, ponieważ pozwolą ci one lepiej zrozumieć istotę sprawy oraz wyćwiczyć umiejętności potrzebne do zrozumienia dalszej partii materiału.

Zadanie 1[2]

Rozkoduj do systemu dziesiętnego liczby:

1.      (13)₇

2.      (666)₇

3.      (666)₁₁

4.      (ABBA.1)₁₃

Praktyka

Jeśli po tych teoretycznych rozważaniach nie bardzo potrafisz wyobrazić sobie to wszystko, nie martw się. Właśnie teraz jest czas i miejsce, by spróbować wyjaśnić systemy liczbowe trochę bardziej „łopatologicznie”.

Wyobraź sobie mechaniczny licznik, np. gazu, prądu, wody, kilometrów lub jakikolwiek inny, który masz w domu albo w samochodzie.

Rysunek 2. Liczba jako mechaniczny licznik z tarczami.

Licznik taki składa się z kilku tarcz, które mogą się obracać. Na ich obwodzie napisane są kolejne cyfry. Granicę między cyfrą ostatnią a pierwszą zaznaczyłem na rysunku niebieską linią (jaki system liczbowy przedstawia rysunek?)[3].

Zasada działania licznika jest następująca: Kręcimy za szarą korbkę powodując obracanie się ostatniej tarczy (tej po prawej stronie). Tarcza pokazuje kolejne cyfry. Kiedy dojdzie do ostatniej i zostanie po raz kolejny obrócona, pokazywała będzie z powrotem pierwszą cyfrę (czyli 0). Dodatkowo spowoduje wtedy przekręcenie następnej tarczy o jedną cyfrę do przodu.

Nietrudno wyobrazić sobie co będzie, kiedy ta druga tarcza osiągnie ostatnią cyfrę. Po następnym obróceniu pokaże 0 oraz spowoduje zwiększenie o jedną pozycję tarczy trzeciej. Ogólnie można powiedzieć, że każdy pełny obrót tarczy poprzedniej powoduje na koniec obrócenie tarczy następnej (na lewo od niej) o jedną pozycję.

Dlatego w systemie dziesiętnym po liczbie 9 następuje liczba 10, a po liczbie 99 występuje liczba 100.

Ćwiczenia

Zadanie 2[4]

Wyprowadź tabelkę kilku kolejnych liczb systemu trójkowego począwszy od 0 korzystając z wyobrażenia liczby jako licznika z tarczami.

Kodowanie liczb całkowitych

Potrafimy już rozkodować liczbę zapisaną w dowolnym systemie na system dziesiętny. Pora nauczyć się kodować liczbę dziesiętną w dowolnym innym systemie.

Nie bój się, nie będzie kolejnego strasznego wzoru :) Takie przeliczanie to czysta praktyka i doskonała zabawa. A więc zaczynamy!

Reszta z dzielenia

Do zabawy potrzebny będzie kalkulator oraz przypomnienie pewnego dawno zapomnianego drobiazgu matematycznego. Zanim jeszcze poznaliśmy w szkole podstawowej ułamki, dzielenie liczb wykonywaliśmy „pod kreskę”. Nad liczbą dzieloną zostawał wynik dzielenia, a na dole otrzymywaliśmy coś, co nazywało się resztą.

Właśnie owa reszta z dzielenia jest czymś, co tutaj i w wielu innych zagadnieniach programistycznych zajmuje bardzo ważne miejsce. Przypomnijmy sobie więc, jak to było…

10:3 = 3.3333…, ale równie dobrze 3 i reszty 1

Dlaczego właśnie 1?

Po pierwsze dlatego, że kiedy pomnożymy wynik dzielenia przez dzielnik, iloczyn będzie się różnił od liczby dzielonej właśnie o resztę (3*3 + 1 = 10).

Po drugie, ponieważ w liczbie 10 trójka „mieści się” 3 razy i zostaje jeszcze liczba 1.

Takie dzielenie z obcięciem reszty nazywane bywa dzieleniem całkowitym, a działanie dające w wyniku samą resztę z dzielenia (z pominięciem właściwego ilorazu) – resztą z dzielenia albo modulo.

Zadanie 3[5]

Używając kalkulatora oblicz, ile będzie wynosiła reszta z dzielenia:

1.      100:10

2.      113:20

3.      512:65

4.      666:7

Popracuj nad metodą obliczania tej reszty i spróbuj zauważyć pewne prawidłowości zachodzące w tym ciekawym działaniu.

Sposób postępowania

OK, pora teraz przejść do sedna sprawy. Naszym zadaniem będzie zakodowanie liczby 1984 w systemie siódemkowym, czyli znalezienie niewiadomej x:

1984 = (x)₇

Algorytm postępowania jest bardzo prosty. Dzielimy liczbę przez podstawę systemu, następnie jako nową liczbę pod spodem zapisujemy wynik, a po prawej stronie zapisujemy resztę z dzielenia. Powtarzamy tą czynność do momentu, kiedy jako wynik z dzielenia otrzymamy 0.

Tabela 16. Kodowanie liczby całkowitej w systemie siódemkowym.

Postaraj się dobrze zrozumieć tą tabelkę. Zwróć też uwagę na ostatnią operację. 5 da się podzielić przez 7. Wtedy reszta wynosi 5, a wynikiem jest 0, co dopiero kończy obliczenia.

Teraz spisujemy cyfry w kolejności od dołu do góry i mamy gotowy wynik :DD

1984 = (5533)₇

Prawda, że to proste?

Ćwiczenia

Zadanie 4[6]

Zakoduj:

1.      liczbę 13 w systemie czwórkowym

2.      liczbę 64 w systemie jedenastkowym

3.      liczbę 666 w systemie dziewiątkowym

4.      liczbę (FF)₁₇ w systemie trójkowym

Kodowanie ułamków

Potrafimy już kodować liczby całkowite. Pora na opanowanie umiejętności kodowania ułamków.

Algorytm postępowania jest bardzo podobny do zamiany liczb całkowitych. Tym razem jednak mnożymy liczbę przez podstawę systemu, jako nową liczbę pod spodem zapisujemy część ułamkową otrzymanego iloczynu (0.cośtam), natomiast część całkowitą (to, co w wyniku otrzymanym po pomnożeniu stało przed przecinkiem) zapisujemy po prawej stronie.

Zakodujmy tym razem liczbę 0.0415 w systemie dwudziestkowym!

Tabela 17. Kodowanie ułamka w systemie dwudziestkowym.

A więc 0.0415 = (0.0GC)₂₀

Tym razem obliczenia zakończyły się otrzymaniem po przecinku wyniku 0 (czyli otrzymaniem liczby całkowitej). Jednak nie zawsze musi tak być. Okazuje się, że liczba posiadająca w pewnym systemie skończone rozwinięcie (skończoną ilość cyfr po przecinku potrzebną do dokładnego zapisania tej liczby) w innym systemie może mieć rozwinięcie nieskończone. Otrzymywalibyśmy wtedy coraz to inne wyniki mnożenia (a może te same? wówczas mielibyśmy do czynienia z ułamkiem okresowym) i w końcu musielibyśmy ograniczyć się do pewnej ustalonej ilości cyfr po przecinku, żeby nie zaliczyć się na śmierć :)

Ćwiczenia

Zadanie 5[7]

Zakoduj:

1.      liczbę 0.3333 w systemie trójkowym

2.      liczbę 0.12 w systemie piątkowym

3.      liczbę 0.777 w systemie piętnastkowym

4.      liczbę 123.456 w systemie ósemkowym

Przelicz jedną z tych liczb z powrotem na system dziesiętny i sprawdź, jak duża niedokładność powstała w związku z obcięciem jej zakodowanej postaci do skończonej ilości cyfr po przecinku.

Algorytm Hornera – dla leniwych

Jeśli wykonałeś zadanie 5 (a na pewno wykonałeś – w końcu jesteś pilnym uczniem, który chce zostać dobrym koderem :) doszedłeś pewnie do wniosku, że zakodować trzeba było osobno część całkowitą i część ułamkową liczby z podpunktu 4. Czy nie istnieje prostszy sposób?

Okazuje się, że tak - nazywa się on algorytmem Hornera. Pozwala on za jednym zamachem zakodować liczbę rzeczywistą posiadającą zarówno część całkowitą, jak i ułamkową.

Jest tylko jedno ograniczenie. Trzeba z góry określić ilość cyfr, na jakiej maksymalnie kodowali będziemy część ułamkową – czyli ilość cyfr po przecinku.

Zakodujemy teraz liczbę 1984.0415 w systemie siódemkowym. Sposób postępowania jest następujący:

Przyjmujemy dokładność do 6 cyfr po przecinku. Następnie mnożymy naszą kodowaną cyfrę przez podstawę systemu podniesioną do potęgi takiej, ile cyfr ustaliliśmy.

1984.0415 * 7⁶ = 1984.0415 * 117 649 = 233 420 498.5

Uff… Tylko spokojnie, nie ma się czego bać. Kalkulator jest po naszej stronie :))

Wyszło coś wielkiego. Co dalej? Najpierw zauważmy, że otrzymana liczba zawiera część ułamkową. Niby nie ma w tym niczego nadzwyczajnego, ale tkwi w tym fakcie pewien szczegół. Otóż obecność w tym iloczynie części ułamkowej informuje nas, że danej liczby nie będzie się dało zakodować z wybraną dokładnością precyzyjnie – zostanie ona obcięta do wybranej ilości cyfr po przecinku.

Po przyjęciu tej informacji do wiadomości zaokrąglamy wynik do liczby całkowitej, a następnie kodujemy ją w wybranym systemie tak, jak koduje się zwyczajne liczby całkowite. Zatem do dzieła!

Tabela 18. Kodowanie liczby algorytmem Hornera.

Nie takie to straszne, jak mogłoby się wydawać. Spisujemy teraz cyfry od dołu do góry, tak jak podczas kodowania liczb całkowitych. Otrzymujemy takie coś: 5533020144.

Na koniec, zgodnie ze wstępnym założeniem, oddzielamy ostatnie 6 cyfr przecinkiem. Ostateczny wynik wygląda tak:

1984.0415 = (5533.020144)₇

Ćwiczenia

Pozostaje nam już tylko przećwiczyć przeliczanie liczb algorytmem Hornera…

Zadanie 6[8]

Zakoduj używając algorytmu Hornera:

1.      liczbę 11.2222 w systemie trójkowym

2.      liczbę 10.5 w systemie piątkowym

3.      liczbę 0.0016 w systemie szesnastkowym

4.      liczbę 2048.128 w systemie dziewiątkowym

Przelicz jedną z tych liczb z powrotem na system dziesiętny i sprawdź, jak duża niedokładność powstała w związku z obcięciem jej zakodowanej postaci do skończonej ilości cyfr po przecinku.

Podsumowanie

W ten oto sposób kończymy podrozdział poświęcony systemom liczbowym i przeliczaniu liczb. Mam nadzieję, że choć trochę poćwiczyłeś takie przeliczanie, posiadłeś umiejętności zamiany wszelkich liczb – małych i dużych – między dowolnymi systemami oraz dobrze się przy tym bawiłeś.

To była taka mała odskocznia od spraw ściśle związanych z komputerem. W następnym podrozdziale już do nich wrócimy.

Zanim jednak to nastąpi, radzę rozwiązać na koniec kilka zadań, które sprawdzą twoją wiedzę i umiejętności nabyte podczas lektury tego podrozdziału.

Zadanie 7[9]

1.      Wyprowadź tabelkę dwudziestu pierwszych liczb systemu jedenastkowego.

2.      Rozkoduj do systemu dziesiętnego liczbę (GG.AG)₁₈.

3.      Ile będzie wynosiła reszta z dzielenia 5555 : 66 ?

4.      Zakoduj dowolną metodą liczbę 2003.1214 w systemie czwórkowym z dokładnością do 10 cyfr po przecinku i rozkoduj ją z powrotem na system dziesiętny. Czy została zachowana dokładność? Po czym to można stwierdzić?

Autor: Adam Sawicki "Regedit"
www.programex.prv.pl
www.regedit.risp.pl
Artykuł jest częścią megatutoriala "Od zera do gier kodera"